Cycle indices of some permutation groups

Identity group $E_n$

This group contains one permutation that fixes every element (this must be a natural action).

Cyclic group $C_n$

A Cyclic group, $C_n$ is the group of rotations of a regular $n$-gon, that is, $n$ elements equally spaced around a circle. This group has $\varphi(d)$ elements of order $d$ for each divisor $d$ of $n$, where $\varphi(d)$ is the Euler φ-function, giving the number of natural numbers less than $d$ which are relatively prime to $d$. In the regular representation of $C_n$, a permutation of order $d$ has $n/d$ cycles of length $d$, thus

Dihedral group $D_n$

The Dihedral group is like the cyclic group, but also includes reflections. In its natural action,

The alternating group $A_n$

The cycle index of the alternating group in its natural action as a permutation group is

The numerator is 2 for the even permutations, and 0 for the odd permutations. The 2 is needed because

The symmetric group $S_n$

The cycle index of the symmetric group$S_n$ in its natural action is given by the formula

This formula is obtained by counting how many times a given permutation shape can occur. There are three steps: first partition the set of $n$ labels into subsets, where there are $j_k$ subsets of size $k$. Every such subset generates $k!/k$ cycles of length $k$. But we do not distinguish between cycles of the same size, i.e. they are permuted by $S_{j_k}$. This yields

There is a useful recursive formula for the cycle index of the symmetric group. Set $Z(S_0) = 1$ and consider the size $l$ of the cycle that contains $n$, where $1 \le l \le n$. There are $\binom{n-1}{l-1}$ ways to choose the remaining $l-1$ elements of the cycle and every such choice generates $\frac{l!}{l}$ different cycles.

This yields the recurrence

or

See also

• Pólya enumeration theorem
• Combinatorial species
• Generating functions